package a_doubleWrite;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * 桶排序
 *
 * @author: luolidong
 * @create: 2021-07-21 22:43
 * @version: 1.0
 */
public class BucketSort {

    public int[] bucketSort(int[] nums) {
        //求最大值，最小值
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < nums.length; i++) {
            max = Math.max(max, nums[i]);
            min = Math.min(min, nums[i]);
        }
        //计算桶的数量，构造桶
        int bucketNum = (max - min) / nums.length + 1;

        List<List<Integer>> list = new ArrayList<>(bucketNum);
        for (int i = 0; i < bucketNum; i++) {
            list.add(new ArrayList<>());
        }

        //放入桶中
        for (int i = 0; i < nums.length; i++) {
            int bucketIndex = (nums[i] - min) / nums.length;
            list.get(bucketIndex).add(nums[i]);
        }

        //排序每个桶中数字
        for (int i = 0; i < bucketNum; i++) {
            Collections.sort(list.get(i));
        }

        //排好的数放回数组
        int startIndex = 0;
        for (int i = 0; i < bucketNum; i++) {
            List<Integer> list1 = list.get(i);
            for (int j = 0; j < list1.size(); j++) {
                nums[startIndex++] = list1.get(j);
            }
        }

        return nums;
    }
}
